
//
// 120304 - AH - Created.
// 120305 - AH - Fixed that suffixes found started one character 'early'.
//

package org.soekrat.engine.dictionary;

import java.io.CharArrayWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * <p>
 *   Simple 
 *   {@link Dictionary} implementation.
 * </p>
 * @author Arne Halvorsen (AH)
 */
public final class SimpleDictionary implements Dictionary 
{
  private final DNode m_root=new DNode();
  
  private int m_size=0;
  
  /**
   * <p>
   *   Node that holds a character in a word.
   * </p>
   * @author Arne Halvorsen (AH)
   */
  private static final class DNode
  {
    private final char m_char;
    
    private DNode m_parent;
    
    private ArrayList<DNode> m_children=null;
    
    /**
     * <p>
     *   Construct root node.
     * </p>
     */
    DNode(){ m_char=' '; m_parent=null; }
    
    /**
     * <p>
     *   Constructor.
     * </p>
     * @param parent Node that represents character before {@code c}.
     * @param c      Character {@code this} node represents.
     */
    DNode(DNode parent, char c)
    {
      m_parent=parent;
      m_char=c;
    }
    
    /**
     * <p>
     *   Gets parent.
     * </p>
     * @return Parent or {@code null} if is root.
     */
    DNode getParent(){ return m_parent; }
    
    /**
     * <p>
     *   Removes child.
     * </p>
     * @param child Child to remove.
     */
    void remove(DNode child)
    {
      if (child==null)
      {
        throw new NullPointerException("child");
      }
      
      if (this!=child.getParent())
      {
        throw new IllegalArgumentException("this not parent");
      }
      
      if (m_children==null || !m_children.remove(child))
      {
        throw new IllegalArgumentException("not a child");  
      }
      
      child.m_parent=null;
    }
    
    /**
     * <p>
     *  Recursively insert a word.
     * </p>
     * @param w   Word being inserted.
     * @param pos Position we are at now.
     * @return {@code true} if word added, {@code false} if already in 
     *         dictionary.
     */
    boolean add(String w, int pos)
    {
      char c=w.charAt(pos);
      
      DNode child=get(c);
      
      if (child==null)
      {
        child=new DNode(this, c);
      
        if (m_children==null) 
        {
          m_children=new ArrayList<DNode>();
        }
        m_children.add(child);
      }
      
      return false;
      
      /*
      if (pos!=w.length()-1) 
      {
        return child.add(w, pos+1);
      }
      else
      {
        if (child.wordEnd()) return false;
        child.wordEnd(true);
        return true;
      }
      */
    }
    
    /**
     * <p>
     *   Recursively search for node last character in given string is
     *   represented with given that given string is a prefix.
     * </p>
     * @param s   {@code String}.
     * @param pos Position in {@code s} we are now at.
     * @return Node or {@code null} if not found.
     */
    DNode getPrefixEnd(String s, int pos)
    {
      char c=s.charAt(pos);
      
      DNode child=get(c);
      
      if (child==null) return null;
      
      if (pos==s.length()-1) return child;
      
      return child.getPrefixEnd(s, pos+1);
    }
    
    void getSuffixes(StringBuilder sb, List<String> l)
    {
      int n=getChildCount();
      for (int i=0; i<n; i++)
      {
        DNode child=m_children.get(i);
        child.getSuffixes_(sb, l);
      }
    }
    
    void getSuffixes_(StringBuilder sb, List<String> l)
    {
      sb.append(m_char);
      if (wordEnd()) l.add(sb.toString());
      
      int length=sb.length();
      
      int n=getChildCount();
      for (int i=0; i<n; i++)
      {
        DNode child=m_children.get(i);
        child.getSuffixes_(sb, l);
        sb.setLength(length);
      }
    }
    
    /**
     * <p>
     *   Sets if a word ends here.
     * </p>
     * @param v {@code true} if does, {@code false} if does not.
     */
    //void wordEnd(boolean v){ m_wordEnd=v; }
    
    /**
     * <p>
     *   Tells if a word ends here.
     * </p>
     * @return {@code true} if does, {@code false} if not.
     */
    boolean wordEnd(){ return false; }
    
    /**
     * <p>
     *   Gets child that represents given character.
     * </p>
     * @param c Character.
     * @return Child or {@code null} if not found.
     */
    DNode get(char c)
    {
      int n=getChildCount();
      for (int i=0; i<n; i++) 
      {
        DNode child=m_children.get(i);
        if (child.m_char==c) return child;
      }
      return null;
    }
    
    /**
     * <p>
     *   Gets number of children.
     * </p>
     * @return Count.
     */
    public int getChildCount()
    {
      int n=(m_children==null) ?  0 : m_children.size();
      return n;
    }
    
    @Override
    public String toString()
    { 
      String s=Character.toString(m_char);
      return wordEnd() ? s+" |" : s;
    }
    
    private void print(PrintWriter pw, String ident)
    {
      pw.println(ident+this);
      ident+="  ";
      int n=getChildCount();
      for (int i=0; i<n; i++)
      {
        m_children.get(i).print(pw, ident);
      }
    }
    
  }

  // Specified in Dictionary.
  public int size(){ return m_size; }

  // Specified in Dictionary.
  public boolean add(String w) 
  {
    if (w==null)
    {
      throw new NullPointerException("w");
    }
    
    w=w.trim();
    if (w.length()==0) return false;
    
    boolean removed=m_root.add(w, 0);
    
    if (removed) m_size++;
    
    return removed;
  }
  
  // Specified in Dictionary.
  public boolean remove(String w)
  {
    if (w==null)
    {
      throw new NullPointerException("w");
    }
    
    w=w.trim();
    
    if (w.length()==0) return false;
    
    DNode curr=m_root.getPrefixEnd(w, 0);
    
    if (curr==null || !curr.wordEnd()) return false;
    
    while (curr!=null)
    {
      //curr.wordEnd(false); TODO
      
      if (curr.getChildCount()>0)
      {
        curr=null;  
      }
      else
      {
        DNode parent=curr.getParent();
      
        parent.remove(curr);
      
        if (parent==m_root)
        {
          curr=null;
        }
        else if (!parent.wordEnd() && parent.getChildCount()>0)
        {
          curr=null;
        }
        else
        {
          curr=parent;
        }
      }
    }
    
    m_size--;
    
    return true;
  }

  // Specified in Dictionary.
  public boolean contains(String w) 
  {
    if (w==null)
    {
      throw new NullPointerException("w");
    }
    
    int wl=w.length();
    
    if (wl==0) return false;
    
    int pos=0;
    int wlm1=wl-1;
    
    DNode node=m_root.get(w.charAt(pos));
    while (node!=null && pos<wlm1)
    {
      pos++;
      node=node.get(w.charAt(pos));
    }
    
    return pos==wlm1 && node.wordEnd();
  }

  // Specified in Dictionary.
  public String[] getSuffixes(String s) 
  {
    if (s==null)
    {
      throw new NullPointerException("s");
    }
    
    s=s.trim();
    
    if (s.length()==0) return E_STRING_A;
    
    DNode prefixEnd=m_root.getPrefixEnd(s, 0);
    
    if (prefixEnd==null) return E_STRING_A;
    
    List<String> suffixes=new ArrayList<String>();
    
    StringBuilder sb=new StringBuilder();
    prefixEnd.getSuffixes(sb, suffixes);
    
    if (suffixes.size()==0) return E_STRING_A;
    
    Collections.sort(suffixes);
    return suffixes.toArray(E_STRING_A);
  }
  
  // Specified in Dictionary.
  public String[] getWords() 
  {
    if (m_size==0) return E_STRING_A;
    
    List<String> suffixes=new ArrayList<String>();
    
    StringBuilder sb=new StringBuilder();
    m_root.getSuffixes_(sb, suffixes);
    
    if (suffixes.size()==0) return E_STRING_A;
    
    Collections.sort(suffixes);
    return suffixes.toArray(E_STRING_A);
  }

  @Override
  public String toString() 
  {
    CharArrayWriter caw=new CharArrayWriter();
    PrintWriter pw=new PrintWriter(caw);
    
    m_root.print(pw, "");
    
    pw.flush();
    return caw.toString();
  }
  
  private final String[] E_STRING_A=new String[0];
  
  public static void main(String[] args) 
  {
    Dictionary dict=new SimpleDictionary();
    
    dict.add("arne");
    dict.add("arne halvorsen");
    dict.add("arne dorkesen");
    
    dict.add("laetitia le chatton");
    dict.add("laetitia le marathon");
    
    System.out.println(dict);
    
    System.out.println("arne: "+dict.contains("arne"));
    System.out.println("arne hal: "+dict.contains("arne hal"));
    System.out.println("arne halvorsen: "+dict.contains("arne halvorsen"));
    System.out.println("arne dorkesen: "+dict.contains("arne dorkesen"));
    System.out.println("laetitia le marathon: "+dict.contains("laetitia le marathon"));
    
    dict.add("arne hal");
    System.out.println(dict);
    System.out.println("arne hal: "+dict.contains("arne hal"));
    
    System.out.println("----");
    
    String[] suffixes=dict.getSuffixes("ar");
    for (String suffix : suffixes) 
    {
      System.out.println(suffix);
    }
    
    System.out.println("----");
    
    System.out.println("all dictionary words:");
    String[] words=dict.getWords();
    for (String suffix : words) 
    {
      System.out.println(suffix);
    }
  }
  
}
